home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / a_utils / _archvrs / unix / zoo21src.lha / zoo / lzd.c < prev    next >
C/C++ Source or Header  |  1992-11-20  |  30KB  |  852 lines
  1. #ifndef LINT
  2. static char sccsid[]="@(#) lzd.c 2.6 88/01/30 20:39:18";
  3. #endif /* LINT */
  4.  
  5. /*********************************************************************/
  6. /* This file contains two versions of the lzd() decompression routine.
  7. The default is to use a fast version coded by Ray Gardner.  If the
  8. symbol SLOW_LZD is defined, the older slower one is used.  I have tested
  9. Ray's code and it seems to be portable and reliable.  But if you
  10. suspect any problems you can define SLOW_LZD for your system in
  11. options.h and cause the older code to be used.  --R.D. */
  12. /*********************************************************************/
  13.  
  14. #include "options.h"
  15. #include "zoo.h"
  16. #include "zooio.h"
  17. #include "various.h"
  18. #include "zoofns.h"           /* function definitions */
  19. #include "zoomem.h"
  20. #include "debug.h"
  21. #include "assert.h"
  22. #include "lzconst.h"
  23.  
  24. #ifndef SLOW_LZD
  25.  
  26. /* Extensive modifications for speed by Ray Gardner
  27. ** Public domain by Raymond D. Gardner  9/26/88
  28. **
  29. ** I apologize for the comments being so dense in places as to impair
  30. ** readability, but some of the stuff isn't very obvious and needs
  31. ** some explaining.  I am also sorry for the messy control structure
  32. ** (quite a few labels and goto's) and very long lzd() function, but
  33. ** I don't know how to do this any other way without loss of speed.
  34. **
  35. ** Ray Gardner
  36. ** 6374 S. Monaco Ct.
  37. ** Englewood, CO 80111
  38. */
  39.  
  40. #ifdef ANSI_HDRS
  41. # include <string.h>        /* to get memcpy */
  42. #else
  43.   VOIDPTR memcpy();
  44. #endif
  45.  
  46. #define  STACKSIZE   4000  /* allows for about 8Mb string in worst case? */
  47. /* stack grows backwards in this version, using pointers, not counters */
  48. static char *stack;
  49. static char *stack_pointer;
  50. static char *stack_lim;
  51.  
  52. void init_dtab PARMS((void));
  53. unsigned rd_dcode PARMS((void));
  54. /* void wr_dchar (char); */        /* now a macro */
  55. void ad_dcode PARMS((void));
  56.  
  57. #ifdef FILTER
  58. /* to send data back to zoofilt */
  59. extern unsigned int filt_lzd_word;
  60. #endif /* FILTER */
  61.  
  62. #ifndef __GNUC__
  63. void xwr_dchar PARMS ((char));
  64. #else
  65. void xwr_dchar PARMS ((int));
  66. #endif /* __GNUC__ */
  67. static int firstchar PARMS ((int));
  68. static void cbfill PARMS ((void));
  69.  
  70. /* wr_dchar() is a macro for speed */
  71. #define wr_dchar(c) {                             \
  72.                            if (outbufp<outbuflim) \
  73.                               *outbufp++=(c);     \
  74.                            else                   \
  75.                               xwr_dchar(c);       \
  76.                     }
  77.  
  78. extern char *out_buf_adr;        /* output buffer */
  79. extern char *in_buf_adr;         /* input buffer */
  80.                       /* use pointers (not counters) for buffer (for speed) */
  81. static char *outbufp;            /* output buffer pointer */
  82. static char *outbuflim;          /* output buffer limit */
  83. static char *outbufguard;        /* output buffer "guard" */
  84.  
  85. char memflag = 0;                /* memory allocated? flag */
  86. int *head;                       /* lzw prefix codes */
  87. char *tail;                      /* lzw suffix codes */
  88. static unsigned cur_code;
  89. static unsigned old_code;
  90. static unsigned in_code;
  91.  
  92. static unsigned free_code;
  93. static int nbits;
  94. static unsigned max_code;
  95.  
  96. /* We use a buffer of codes to avoid a function call to unpack each
  97. ** one as needed.  We allocate an extra slot past the end of the buffer
  98. ** and put a CLEAR code in it, to serve as a sentinel.  This way we can
  99. ** fold the test for code buffer runout into the test for a clear code
  100. ** and avoid having an extra test on each code processed.  Also, we don't
  101. ** always use the code buffer.  We can only use it when the input buffer
  102. ** is at a byte boundary, and when we know that the codesize won't change
  103. ** before we fill the code buffer, and when we know we won't run out of
  104. ** bytes in the input buffer before filling the code buffer.  So we start
  105. ** with the code buffer pointer pointing to the sentinel, and we always
  106. ** have it pointing at the sentinel when we can't (for one reason or
  107. ** another) be getting our codes from the code buffer.  We check for this
  108. ** condition whenever we get a CLEAR code, and if so, we get the code
  109. ** via the good old rd_dcode() routine.
  110. **
  111. ** One other problem with the code buffer approach is that we might get
  112. ** a CLEAR code in the middle of the buffer.  This means that the next
  113. ** code is only 9 bits, but we have probably already unpacked a number of
  114. ** larger codes from the input into the buffer before we discover this.
  115. ** So we remember where (in the input buffer) the code buffer was filled
  116. ** from, and when a CLEAR code is encountered in the buffer (not the
  117. ** sentinel at the end) we back up the bit_offset pointer in the input
  118. ** buffer, and reset things to start unpacking the 9-bit codes from there.
  119. */
  120.  
  121. #define CODEBUF_SIZE 64      /* must be multiple of 8, experiment for best */
  122. static unsigned codebuf[CODEBUF_SIZE+1];     /* code buffer */
  123. static unsigned *codebufp;       /* code buffer pointer */
  124. static unsigned *codebuflim;     /* code buffer limit */
  125.       /* bit offset within the input buffer of where the code buffer began */
  126. static unsigned codebufoffset;
  127.  
  128. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  129.                         0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  130. static unsigned bit_offset;   /* note this only allows max 8K input buffer!!*/
  131.  
  132. #ifdef UNBUF_IO
  133. #define        BLOCKFILE        int
  134. #define        BLOCKREAD        read
  135. #define        BLOCKWRITE        blockwrite
  136. int read PARMS ((int, VOIDPTR, unsigned));
  137. int write PARMS ((int, VOIDPTR, unsigned));
  138. int blockwrite PARMS ((int, VOIDPTR, unsigned));
  139. #else
  140. #define        BLOCKFILE        ZOOFILE
  141. #define        BLOCKREAD        zooread
  142. #define        BLOCKWRITE        zoowrite
  143. #endif /* UNBUF_IO */
  144.  
  145. static BLOCKFILE in_f, out_f;
  146.  
  147. /* rd_dcode() reads a code from the input (compressed) file and returns
  148. its value. */
  149. unsigned rd_dcode()
  150. {
  151.    register char *ptra, *ptrb;    /* miscellaneous pointers */
  152.    unsigned word;                     /* first 16 bits in buffer */
  153.    unsigned byte_offset;
  154.    char nextch;                           /* next 8 bits in buffer */
  155.    unsigned ofs_inbyte;               /* offset within byte */
  156.  
  157.    ofs_inbyte = bit_offset % 8;
  158.    byte_offset = bit_offset / 8;
  159.    bit_offset = bit_offset + nbits;
  160.  
  161.    assert(nbits >= 9 && nbits <= 13);
  162.  
  163.    if (byte_offset >= INBUFSIZ - 5) {
  164.       int space_left;
  165.  
  166.       assert(byte_offset >= INBUFSIZ - 5);
  167.       debug((printf ("lzd: byte_offset near end of buffer\n")))
  168.  
  169.       bit_offset = ofs_inbyte + nbits;
  170.       space_left = INBUFSIZ - byte_offset;
  171.       ptrb = byte_offset + in_buf_adr;          /* point to char */
  172.       ptra = in_buf_adr;
  173.       /* we now move the remaining characters down buffer beginning */
  174.       debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  175.       while (space_left > 0) {
  176.          *ptra++ = *ptrb++;
  177.          space_left--;
  178.       }
  179.       assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  180.       assert(space_left == 0);
  181.       if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
  182.          prterror ('f', "I/O error in lzd:rd_dcode.\n");
  183.       byte_offset = 0;
  184.    }
  185.    ptra = byte_offset + in_buf_adr;
  186.  /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  187.    word = (unsigned char) *ptra; ptra++;
  188.    word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;
  189.  
  190.    nextch = *ptra;
  191.    if (ofs_inbyte != 0) {
  192.       /* shift nextch right by ofs_inbyte bits */
  193.       /* and shift those bits right into word; */
  194.       word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  195.    }
  196.    return (word & masks[nbits]); 
  197. } /* rd_dcode() */
  198.  
  199. void init_dtab()
  200. {
  201.    nbits = 9;
  202.    max_code = 512;
  203.    free_code = FIRST_FREE;
  204. }
  205.  
  206. /* By making wr_dchar() a macro and calling this routine only on buffer
  207. ** full condition, we save a lot of function call overhead.
  208. ** We also use pointers instead of counters for efficiency (in the macro).
  209. */
  210. void xwr_dchar (ch)
  211. char ch;
  212. {
  213.    if (outbufp >= outbuflim) {      /* if buffer full */
  214.       if (BLOCKWRITE (out_f, out_buf_adr, (outbufp - out_buf_adr))
  215.                                                 != outbufp - out_buf_adr)
  216.          prterror ('f', "Write error in lzd:wr_dchar.\n");
  217.       addbfcrc(out_buf_adr, outbufp - out_buf_adr);     /* update CRC */
  218.       outbufp = out_buf_adr;                  /* restore empty buffer */
  219.    }
  220.    assert(outbufp - out_buf_adr < OUTBUFSIZ);
  221.    *outbufp++ = ch;
  222. } /* wr_dchar() */
  223.  
  224.  
  225. /* Code buffer fill routines
  226. **
  227. ** We use a separate function for each code size.
  228. ** Each function unpacks 8 codes from a packed buffer (f)
  229. ** to an unpacked buffer (t)
  230. ** A lot of code space, but really speeds up bit picking.
  231. */
  232. static unsigned char f[13];   /* must be unsigned for right shifts */
  233. static unsigned t[8];
  234.  
  235. static void cb9fill ()
  236. {
  237.    t[0] = (f[0]     ) | ((f[1] &   1) << 8);
  238.    t[1] = (f[1] >> 1) | ((f[2] &   3) << 7);
  239.    t[2] = (f[2] >> 2) | ((f[3] &   7) << 6);
  240.    t[3] = (f[3] >> 3) | ((f[4] &  15) << 5);
  241.    t[4] = (f[4] >> 4) | ((f[5] &  31) << 4);
  242.    t[5] = (f[5] >> 5) | ((f[6] &  63) << 3);
  243.    t[6] = (f[6] >> 6) | ((f[7] & 127) << 2);
  244.    t[7] = (f[7] >> 7) | ((f[8]      ) << 1);
  245. }
  246.  
  247. static void cb10fill ()
  248. {
  249.    t[0] = (f[0]     ) | ((f[1] &   3) << 8);
  250.    t[1] = (f[1] >> 2) | ((f[2] &  15) << 6);
  251.    t[2] = (f[2] >> 4) | ((f[3] &  63) << 4);
  252.    t[3] = (f[3] >> 6) | ((f[4]      ) << 2);
  253.    t[4] = (f[5]     ) | ((f[6] &   3) << 8);
  254.    t[5] = (f[6] >> 2) | ((f[7] &  15) << 6);
  255.    t[6] = (f[7] >> 4) | ((f[8] &  63) << 4);
  256.    t[7] = (f[8] >> 6) | ((f[9]      ) << 2);
  257. }
  258.  
  259. static void cb11fill ()
  260. {
  261.    t[0] = (f[0]     ) | ((f[1] &   7) << 8);
  262.    t[1] = (f[1] >> 3) | ((f[2] &  63) << 5);
  263.    t[2] = (f[2] >> 6) | (f[3] << 2) | ((f[4] &  1) << 10);
  264.    t[3] = (f[4] >> 1) | ((f[5] &  15) << 7);
  265.    t[4] = (f[5] >> 4) | ((f[6] & 127) << 4);
  266.    t[5] = (f[6] >> 7) | (f[7] << 1) | ((f[8] &  3) <<  9);
  267.    t[6] = (f[8] >> 2) | ((f[9] &  31) << 6);
  268.    t[7] = (f[9] >> 5) | ((f[10]     ) << 3);
  269. }
  270.  
  271. static void cb12fill ()
  272. {
  273.    t[0] = (f[0]     )  | ((f[1] & 15) << 8);
  274.    t[1] = (f[1] >> 4)  | ((f[2]     ) << 4);
  275.    t[2] = (f[3]     )  | ((f[4] & 15) << 8);
  276.    t[3] = (f[4] >> 4)  | ((f[5]     ) << 4);
  277.    t[4] = (f[6]     )  | ((f[7] & 15) << 8);
  278.    t[5] = (f[7] >> 4)  | ((f[8]     ) << 4);
  279.    t[6] = (f[9]     )  | ((f[10] & 15) << 8);
  280.    t[7] = (f[10] >> 4) | ((f[11]     ) << 4);
  281. }
  282.  
  283. static void cb13fill ()
  284. {
  285.    t[0] = (f[0] ) | ((f[1] & 31) << 8);
  286.    t[1] = (f[1] >> 5) | (f[2] << 3) | ((f[3] & 3) << 11);
  287.    t[2] = (f[3] >> 2) | ((f[4] & 127) << 6);
  288.    t[3] = (f[4] >> 7) | (f[5] << 1) | ((f[6] & 15) << 9);
  289.    t[4] = (f[6] >> 4) | (f[7] << 4) | ((f[8] & 1) << 12);
  290.    t[5] = (f[8] >> 1) | ((f[9] & 63) << 7);
  291.    t[6] = (f[9] >> 6) | (f[10] << 2) | ((f[11] & 7) << 10);
  292.    t[7] = (f[11] >> 3) | (f[12] << 5);
  293. }
  294.  
  295. /* vector of code buffer fill routines
  296. */
  297. void (*cbfillvec[])  PARMS ((void)) = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  298.          cb9fill, cb10fill, cb11fill, cb12fill, cb13fill };
  299.  
  300. /* cbfill -- main code buffer fill routine
  301. **
  302. ** moves data from inbuf[] to f[]
  303. ** then calls via vector to unpack to t[]
  304. ** then moves from t[] to codebuf[]
  305. ** A lot of moving around, but still faster than a lot of shifting and
  306. ** masking via variables (at least on a micro -- don't know about VAXen)
  307. **  Uses memcpy() for block move
  308. */
  309.  
  310. static void cbfill ()
  311. {
  312.    char *inbp;
  313.    inbp = in_buf_adr + bit_offset / 8;
  314.    codebufp = codebuf;
  315.    while ( codebufp < codebuflim ) {
  316.      memcpy((VOIDPTR) f, inbp, nbits);
  317.       (*cbfillvec[nbits])();
  318.       memcpy((VOIDPTR) codebufp, (VOIDPTR) t, 8 * sizeof(unsigned int));
  319.       inbp += nbits;
  320.       codebufp += 8;
  321.    }
  322.    bit_offset += nbits * CODEBUF_SIZE;
  323. }
  324.  
  325. /* The following is used in the KwKwK case because it's a pretty rare
  326. ** case, and doing it this way avoids the overhead of remembering the
  327. ** "finchar" (first input character) of every string
  328. */
  329. static int firstchar(code)    /* find first character of a code */
  330. int code;
  331. {
  332.    while ( code > 255 )
  333.       code = head[code];
  334.    return code;
  335. }
  336.  
  337. int lzd(input_f, output_f)
  338. BLOCKFILE input_f, output_f;          /* input & output files */
  339. {
  340.    in_f = input_f;                 /* make it avail to other fns */
  341.    out_f = output_f;               /* ditto */
  342.    nbits = 9;
  343.    max_code = 512;
  344.    free_code = FIRST_FREE;
  345.    bit_offset = 0;
  346.    outbuflim = out_buf_adr + OUTBUFSIZ;   /* setup out buffer limit */
  347.    outbufguard = outbuflim - 12;     /* for checking avail. room in outbuf */
  348.       /* note must allow for as many characters as we special-case (8) */
  349.       /* used 12 for extra fudge factor (Rahul does it, so I can too) */
  350.    outbufp = out_buf_adr;                 /* setup output buffer ptr */ 
  351.    codebufp = codebuflim = &codebuf[CODEBUF_SIZE]; /* code buf ptr & limit */
  352.    *codebuflim = CLEAR; /* phony CLEAR sentinel past end of code buffer */
  353.  
  354.    if (BLOCKREAD (in_f, in_buf_adr, INBUFSIZ) == -1) /* fill input buffer */
  355.       return(IOERR);
  356.    if (memflag == 0) {
  357.      head = (int *) ealloc((MAXMAX+10) * sizeof(int));
  358.      tail = (char *) ealloc((MAXMAX+10) * sizeof(char));
  359.      stack = (char *) ealloc (sizeof (unsigned) * STACKSIZE + 20);
  360.      memflag++;
  361.    }
  362.  
  363.    stack_pointer = stack_lim = stack + STACKSIZE; /* setup stack ptr, limit*/
  364.    init_dtab();             /* initialize table */
  365.  
  366. loop:
  367.    cur_code = *codebufp++; /* get code from code buffer */
  368.  
  369. goteof: /* special case for CLEAR then Z_EOF, for 0-length files */
  370.    if (cur_code == Z_EOF) {
  371.       debug((printf ("lzd: Z_EOF\n")))
  372.  
  373.       if (outbufp != out_buf_adr) {
  374.           if (BLOCKWRITE (out_f, out_buf_adr, (outbufp - out_buf_adr))
  375.                                                   != outbufp - out_buf_adr)
  376.              prterror ('f', "Output error in lzd().\n");
  377.             addbfcrc(out_buf_adr, outbufp - out_buf_adr);
  378.  
  379.       }
  380. #ifdef FILTER
  381.         /* get next two bytes and put them where zoofilt can find them */
  382.         /* nbits known to be in range 9..13 */
  383.         bit_offset = ((bit_offset + 7) / 8) * 8; /* round up to next byte */
  384.         filt_lzd_word = rd_dcode();
  385.         filt_lzd_word |= (rd_dcode() << nbits);
  386.         filt_lzd_word &= 0xffff;
  387. #endif
  388.       return (0);
  389.    }
  390.  
  391.    assert(nbits >= 9 && nbits <= 13);
  392.  
  393.    if (cur_code == CLEAR) {          /* was it sentinel or real CLEAR ? */
  394.       if ( codebufp > codebuflim ) { /* it was the sentinel             */
  395.          if ( bit_offset % 8 == 0 && /* if we're on byte boundary and   */
  396.                    /* codesize won't change before codebuf is filled and */
  397.                    /* codebuf can be filled without running out of inbuf */
  398.                 free_code + CODEBUF_SIZE < max_code &&
  399.                 bit_offset / 8 + (CODEBUF_SIZE * 13 / 8) < INBUFSIZ - 10 ) {
  400.             codebufoffset = bit_offset; /* remember where we were when */
  401.             cbfill();             /* we filled the code buffer */
  402.             codebufp = codebuf;   /* setup code buffer pointer */
  403.             goto loop;            /* now go get codes from code buffer */
  404.          }                 /* otherwise, use rd_dcode to get code */
  405.          codebufp = codebuflim;   /* reset codebuf ptr to sentinel */
  406.          cur_code = rd_dcode();   /* get code via rd_dcode() */
  407.          if ( cur_code != CLEAR ) /* if it's not CLEAR */
  408.             goto got_code;        /* then go handle it */
  409.       } else {          /* else it's really a CLEAR code, not sentinel */
  410.  /* reset bit_offset to get next code in input buf after CLEAR code */
  411.          bit_offset = codebufoffset + (codebufp - codebuf) * nbits;
  412.       } 
  413.       codebufp = codebuflim;      /* set code buf ptr to sentinel */
  414.       debug((printf ("lzd: CLEAR\n")))
  415.       init_dtab();                /* init decompression table, etc. */
  416.       old_code = cur_code = rd_dcode(); /* get next code after CLEAR */
  417.         if (cur_code == Z_EOF)        /* special case for 0-length files */
  418.             goto goteof;
  419.       wr_dchar(cur_code);         /* write it out */
  420.       goto loop;                  /* and get next code */
  421.    }
  422.  
  423. got_code: /* we got a code and it's not a CLEAR */
  424.  
  425.    if (cur_code == Z_EOF) {
  426.       debug((printf ("lzd: Z_EOF\n")))
  427.       if (outbufp != out_buf_adr) {
  428.           if (BLOCKWRITE (out_f, out_buf_adr, (outbufp - out_buf_adr))
  429.                                                   != outbufp - out_buf_adr)
  430.              prterror ('f', "Output error in lzd().\n");
  431.          addbfcrc(out_buf_adr, outbufp - out_buf_adr);
  432.       }
  433.       return (0);
  434.    }
  435.  
  436.    in_code = cur_code;              /* save original code */
  437.    if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
  438.       cur_code = old_code;             /* previous code becomes current */
  439.                                        /* push first character of old code */
  440.       *--stack_pointer = firstchar(old_code);
  441.       goto unwind;                     /* and go "unwind" the current code */
  442.    }              /* (use general unwind because the stack isn't empty now) */
  443.  
  444. /* Unwind a code.  The basic idea is to use a sort of loop-unrolling
  445. ** approach to really speed up the processing by treating the codes
  446. ** which represent short strings (the vast majority of codes) as
  447. ** special cases.  Avoid a lot of stack overflow checking safely.
  448. */
  449.  
  450.    if (cur_code > 255) {                  /* if cur_code is not atomic */
  451.       *--stack_pointer = tail[cur_code];  /* push its tail code */
  452.       cur_code = head[cur_code];          /* and replace with its head code */
  453.    } else {                        /* else 1-byte string */
  454.       if ( outbufp > outbufguard ) /* if outbuf near end, */
  455.          goto write_stack;         /* write via general routine */
  456.       *outbufp++ = cur_code;       /* we got space, put char out */
  457.       goto add_code;               /* add code to table */
  458.    }
  459.  
  460.    if (cur_code > 255) {                  /* if cur_code is not atomic */
  461.       *--stack_pointer = tail[cur_code];  /* push its tail code */
  462.       cur_code = head[cur_code];          /* and replace with its head code */
  463.    } else {                        /* else 2-byte string */
  464.       if ( outbufp > outbufguard ) /* if outbuf near end, */
  465.          goto write_stack;         /* write via general routine */
  466.       *outbufp++ = cur_code;       /* we got space, put char out, and */
  467.       goto move_1_char;            /* go move rest of stack to outbuf */
  468.    }
  469.    if (cur_code > 255) {                  /* if cur_code is not atomic */
  470.       *--stack_pointer = tail[cur_code];  /* push its tail code */
  471.       cur_code = head[cur_code];          /* and replace with its head code */
  472.    } else {                        /* else 3-byte string */
  473.       if ( outbufp > outbufguard ) /* if outbuf near end, */
  474.          goto write_stack;         /* write via general routine */
  475.       *outbufp++ = cur_code;       /* we got space, put char out, and */
  476.       goto move_2_char;            /* go move rest of stack to outbuf */
  477.    }
  478.  
  479. /* we handle codes representing strings of 4 thru 8 bytes similarly */
  480.  
  481.    if (cur_code > 255) {
  482.       *--stack_pointer = tail[cur_code];
  483.       cur_code = head[cur_code];
  484.    } else {                        /* 4-byte string */
  485.       if ( outbufp > outbufguard )
  486.          goto write_stack;
  487.       *outbufp++ = cur_code;
  488.       goto move_3_char;
  489.    }
  490.    if (cur_code > 255) {
  491.       *--stack_pointer = tail[cur_code];
  492.       cur_code = head[cur_code];
  493.    } else {                        /* 5-byte string */
  494.       if ( outbufp > outbufguard )
  495.          goto write_stack;
  496.       *outbufp++ = cur_code;
  497.       goto move_4_char;
  498.    }
  499.    if (cur_code > 255) {
  500.       *--stack_pointer = tail[cur_code];
  501.       cur_code = head[cur_code];
  502.    } else {                        /* 6-byte string */
  503.       if ( outbufp > outbufguard )
  504.          goto write_stack;
  505.       *outbufp++ = cur_code;
  506.       goto move_5_char;
  507.    }
  508.    if (cur_code > 255) {
  509.       *--stack_pointer = tail[cur_code];
  510.       cur_code = head[cur_code];
  511.    } else {                        /* 7-byte string */
  512.       if ( outbufp > outbufguard )
  513.          goto write_stack;
  514.       *outbufp++ = cur_code;
  515.       goto move_6_char;
  516.    }
  517.    if (cur_code > 255) {
  518.       *--stack_pointer = tail[cur_code];
  519.       cur_code = head[cur_code];
  520.    } else {                        /* 8-byte string */
  521.       if ( outbufp > outbufguard )
  522.          goto write_stack;
  523.       *outbufp++ = cur_code;
  524.       goto move_7_char;
  525.    }
  526.  
  527. /* Here for KwKwK case and strings longer than 8 bytes */
  528. /* Note we have to check stack here, but not elsewhere */
  529.  
  530. unwind:
  531.    while (cur_code > 255) {               /* if code, not character */
  532.       *--stack_pointer = tail[cur_code];         /* push suffix char */
  533.       if (stack_pointer < stack+12)
  534.          prterror ('f', "Stack overflow in lzd().\n");
  535.       cur_code = head[cur_code];          /* head of code is new code */
  536.    }
  537.  
  538. /* General routine to write stack with check for output buffer full */
  539.  
  540. write_stack:
  541.    assert(nbits >= 9 && nbits <= 13);
  542.    wr_dchar(cur_code);    /* write this code, don't need to stack it first */
  543.    while ( stack_pointer < stack_lim ) {
  544.       wr_dchar(*stack_pointer++);
  545.    }
  546.    goto add_code;                           /* now go add code to table */
  547.  
  548. /* Here to move strings from stack to output buffer */
  549. /* only if we know we have enough room in output buffer */
  550. /* because (outbufp <= outbufguard) */
  551.  
  552. move_7_char:
  553.    *outbufp++ = *stack_pointer++;
  554. move_6_char:
  555.    *outbufp++ = *stack_pointer++;
  556. move_5_char:
  557.    *outbufp++ = *stack_pointer++;
  558. move_4_char:
  559.    *outbufp++ = *stack_pointer++;
  560. move_3_char:
  561.    *outbufp++ = *stack_pointer++;
  562. move_2_char:
  563.    *outbufp++ = *stack_pointer++;
  564. move_1_char:
  565.    *outbufp++ = *stack_pointer++;
  566.  
  567. assert(stack_pointer == stack_lim); /* I haven't tested this! rdg */
  568.  
  569. /* add_code is now inline to avoid overhead of function call on */
  570. /*   each code processed */
  571.  
  572. add_code:
  573.    assert(nbits >= 9 && nbits <= 13);
  574.    assert(free_code <= MAXMAX+1);
  575.    tail[free_code] = cur_code;                /* save suffix char */
  576.    head[free_code] = old_code;                /* save prefix code */
  577.    free_code++;
  578.    assert(nbits >= 9 && nbits <= 13);
  579.    if (free_code >= max_code) {
  580.       if (nbits < MAXBITS) {
  581.          debug((printf("lzd: nbits was %d\n", nbits)))
  582.          nbits++;
  583.          assert(nbits >= 9 && nbits <= 13);
  584.          debug((printf("lzd: nbits now %d\n", nbits)))
  585.          max_code = max_code << 1;        /* double max_code */
  586.          debug((printf("lzd: max_code now %d\n", max_code)))
  587.       }
  588.    }
  589.    old_code = in_code;
  590.  
  591.    assert(nbits >= 9 && nbits <= 13);
  592.  
  593.    goto loop;
  594. } /* lzd() */
  595.  
  596. #else /* SLOW_LZD defined, so use following instead */
  597.  
  598. /*********************************************************************/
  599. /* Original slower lzd().                                            */
  600. /*********************************************************************/
  601.  
  602. /*
  603. Lempel-Ziv decompression.  Mostly based on Tom Pfau's assembly language
  604. code.  The contents of this file are hereby released to the public domain.
  605.                                  -- Rahul Dhesi 1986/11/14
  606. */
  607.  
  608. #define  STACKSIZE   4000
  609.  
  610. struct tabentry {
  611.    unsigned next;
  612.    char z_ch;
  613. };
  614.  
  615. void init_dtab PARMS((void));
  616. unsigned rd_dcode PARMS((void));
  617. void wr_dchar PARMS((int));
  618. void ad_dcode PARMS((void));
  619.  
  620. #ifdef FILTER
  621. /* to send data back to zoofilt */
  622. extern unsigned int filt_lzd_word;
  623. #endif /* FILTER */
  624.  
  625.  
  626. static unsigned stack_pointer = 0;
  627. static unsigned *stack;
  628.  
  629. #define  push(x)  {  \
  630.                      stack[stack_pointer++] = (x);                   \
  631.                      if (stack_pointer >= STACKSIZE)                 \
  632.                         prterror ('f', "Stack overflow in lzd().\n");\
  633.                   }
  634. #define  pop()    (stack[--stack_pointer])
  635.  
  636. extern char *out_buf_adr;        /* output buffer */
  637. extern char *in_buf_adr;         /* input buffer */
  638.  
  639. char memflag = 0;                /* memory allocated? flag */
  640. extern struct tabentry *table;   /* hash table from lzc.c */
  641. static unsigned cur_code;
  642. static unsigned old_code;
  643. static unsigned in_code;
  644.  
  645. static unsigned free_code;
  646. static int nbits;
  647. static unsigned max_code;
  648.  
  649. static char fin_char;
  650. static char k;
  651. static unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  652.                         0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  653. static unsigned bit_offset;
  654. static unsigned output_offset;
  655.  
  656. #ifdef UNBUF_IO
  657. #define        BLOCKFILE        int
  658. #define        BLOCKREAD        read
  659. #define        BLOCKWRITE        blockwrite
  660. int read PARMS ((int, VOIDPTR, unsigned));
  661. int write PARMS ((int, VOIDPTR, unsigned));
  662. #else
  663. #define        BLOCKFILE        ZOOFILE
  664. #define        BLOCKREAD        zooread
  665. #define        BLOCKWRITE        zoowrite
  666. #endif /* UNBUF_IO */
  667.  
  668. static BLOCKFILE in_f, out_f; 
  669.  
  670. int lzd(input_f, output_f)
  671. BLOCKFILE input_f, output_f;          /* input & output file handles */
  672. {
  673.    in_f = input_f;                 /* make it avail to other fns */
  674.    out_f = output_f;               /* ditto */
  675.    nbits = 9;
  676.    max_code = 512;
  677.    free_code = FIRST_FREE;
  678.    stack_pointer = 0;
  679.    bit_offset = 0;
  680.    output_offset = 0;
  681.  
  682.    if (BLOCKREAD (in_f, in_buf_adr, INBUFSIZ) == -1)
  683.       return(IOERR);
  684.    if (memflag == 0) {
  685.      table = (struct tabentry *) ealloc((MAXMAX+10) * sizeof(struct tabentry));
  686.      stack = (unsigned *) ealloc (sizeof (unsigned) * STACKSIZE + 20);
  687.      memflag++;
  688.    }
  689.  
  690.    init_dtab();             /* initialize table */
  691.  
  692. loop:
  693.    cur_code = rd_dcode();
  694. goteof: /* special case for CLEAR then Z_EOF, for 0-length files */
  695.    if (cur_code == Z_EOF) {
  696.       debug((printf ("lzd: Z_EOF\n")))
  697.       if (output_offset != 0) {
  698.          if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
  699.             prterror ('f', "Output error in lzd().\n");
  700.          addbfcrc(out_buf_adr, output_offset);
  701.       }
  702. #ifdef FILTER
  703.         /* get next two bytes and put them where zoofilt can find them */
  704.         /* nbits known to be in range 9..13 */
  705.         bit_offset = ((bit_offset + 7) / 8) * 8; /* round up to next byte */
  706.         filt_lzd_word = rd_dcode();
  707.         filt_lzd_word |= (rd_dcode() << nbits);
  708.         filt_lzd_word &= 0xffff;
  709. #endif
  710.       return (0);
  711.    }
  712.  
  713.    assert(nbits >= 9 && nbits <= 13);
  714.  
  715.    if (cur_code == CLEAR) {
  716.       debug((printf ("lzd: CLEAR\n")))
  717.       init_dtab();
  718.       fin_char = k = old_code = cur_code = rd_dcode();
  719.         if (cur_code == Z_EOF)        /* special case for 0-length files */
  720.             goto goteof;
  721.       wr_dchar(k);
  722.       goto loop;
  723.    }
  724.  
  725.    in_code = cur_code;
  726.    if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
  727.       cur_code = old_code;             /* previous code becomes current */
  728.       push(fin_char);
  729.    }
  730.  
  731.    while (cur_code > 255) {               /* if code, not character */
  732.       push(table[cur_code].z_ch);         /* push suffix char */
  733.       cur_code = table[cur_code].next;    /* <w> := <w>.code */
  734.    }
  735.  
  736.    assert(nbits >= 9 && nbits <= 13);
  737.  
  738.    k = fin_char = cur_code;
  739.    push(k);
  740.    while (stack_pointer != 0) {
  741.       wr_dchar(pop());
  742.    }
  743.    assert(nbits >= 9 && nbits <= 13);
  744.    ad_dcode();
  745.    old_code = in_code;
  746.  
  747.    assert(nbits >= 9 && nbits <= 13);
  748.  
  749.    goto loop;
  750. } /* lzd() */
  751.  
  752. /* rd_dcode() reads a code from the input (compressed) file and returns
  753. its value. */
  754. unsigned rd_dcode()
  755. {
  756.    register char *ptra, *ptrb;    /* miscellaneous pointers */
  757.    unsigned word;                     /* first 16 bits in buffer */
  758.    unsigned byte_offset;
  759.    char nextch;                           /* next 8 bits in buffer */
  760.    unsigned ofs_inbyte;               /* offset within byte */
  761.  
  762.    ofs_inbyte = bit_offset % 8;
  763.    byte_offset = bit_offset / 8;
  764.    bit_offset = bit_offset + nbits;
  765.  
  766.    assert(nbits >= 9 && nbits <= 13);
  767.  
  768.    if (byte_offset >= INBUFSIZ - 5) {
  769.       int space_left;
  770.  
  771. #ifdef CHECK_BREAK
  772.     check_break();
  773. #endif
  774.  
  775.       assert(byte_offset >= INBUFSIZ - 5);
  776.       debug((printf ("lzd: byte_offset near end of buffer\n")))
  777.  
  778.       bit_offset = ofs_inbyte + nbits;
  779.       space_left = INBUFSIZ - byte_offset;
  780.       ptrb = byte_offset + in_buf_adr;          /* point to char */
  781.       ptra = in_buf_adr;
  782.       /* we now move the remaining characters down buffer beginning */
  783.       debug((printf ("rd_dcode: space_left = %d\n", space_left)))
  784.       while (space_left > 0) {
  785.          *ptra++ = *ptrb++;
  786.          space_left--;
  787.       }
  788.       assert(ptra - in_buf_adr == ptrb - (in_buf_adr + byte_offset));
  789.       assert(space_left == 0);
  790.       if (BLOCKREAD (in_f, ptra, byte_offset) == -1)
  791.          prterror ('f', "I/O error in lzd:rd_dcode.\n");
  792.       byte_offset = 0;
  793.    }
  794.    ptra = byte_offset + in_buf_adr;
  795.    /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  796.    word = (unsigned char) *ptra; ptra++;
  797.    word = word | ( ((unsigned char) *ptra) << 8 ); ptra++;
  798.  
  799.    nextch = *ptra;
  800.    if (ofs_inbyte != 0) {
  801.       /* shift nextch right by ofs_inbyte bits */
  802.       /* and shift those bits right into word; */
  803.       word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  804.    }
  805.    return (word & masks[nbits]); 
  806. } /* rd_dcode() */
  807.  
  808. void init_dtab()
  809. {
  810.    nbits = 9;
  811.    max_code = 512;
  812.    free_code = FIRST_FREE;
  813. }
  814.  
  815. void wr_dchar (ch)
  816. int ch;
  817. {
  818.    if (output_offset >= OUTBUFSIZ) {      /* if buffer full */
  819. #ifdef CHECK_BREAK
  820.     check_break();
  821. #endif
  822.       if (BLOCKWRITE (out_f, out_buf_adr, output_offset) != output_offset)
  823.          prterror ('f', "Write error in lzd:wr_dchar.\n");
  824.       addbfcrc(out_buf_adr, output_offset);     /* update CRC */
  825.       output_offset = 0;                  /* restore empty buffer */
  826.    }
  827.    assert(output_offset < OUTBUFSIZ);
  828.    out_buf_adr[output_offset++] = ch;        /* store character */
  829. } /* wr_dchar() */
  830.  
  831. /* adds a code to table */
  832. void ad_dcode()
  833. {
  834.    assert(nbits >= 9 && nbits <= 13);
  835.    assert(free_code <= MAXMAX+1);
  836.    table[free_code].z_ch = k;                /* save suffix char */
  837.    table[free_code].next = old_code;         /* save prefix code */
  838.    free_code++;
  839.    assert(nbits >= 9 && nbits <= 13);
  840.    if (free_code >= max_code) {
  841.       if (nbits < MAXBITS) {
  842.          debug((printf("lzd: nbits was %d\n", nbits)))
  843.          nbits++;
  844.          assert(nbits >= 9 && nbits <= 13);
  845.          debug((printf("lzd: nbits now %d\n", nbits)))
  846.          max_code = max_code << 1;        /* double max_code */
  847.          debug((printf("lzd: max_code now %d\n", max_code)))
  848.       }
  849.    }
  850. }
  851. #endif /* ! SLOW_LZD */
  852.